﻿#define TFS_MEMOIZED
//#define MANUAL_SET_EVENT

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Threading;

using agree.schema;

using alib.Collections;
using alib.Collections.ReadOnly;
using alib.Reflection;
using alib.Concurrency;
using alib.Debugging;
using alib.Enumerable;
using alib.String;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public struct ChartObjHelper<W>
		 where W : struct, IProximalContext<W>
	{
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IChartObj<W> m_next;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IChartObj<W> Next { get { return m_next; } }

		public bool TrySetNext(IChartObj a, IChartObj b)
		{
			return Interlocked.CompareExchange(ref m_next, (IChartObj<W>)a, (IChartObj<W>)b) == b;
		}

		public IChartObj<W> AddToList(IChartObj po_to_add, ref long next_obj_id)
		{
			IChartObj<W> r = m_next, pta = (IChartObj<W>)po_to_add;
			if (r == null && (r = Interlocked.CompareExchange(ref m_next, pta, null)) == null)
				pta.SetSequenceId(ref next_obj_id);
			return r;
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// IDerivation helper value-type
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public struct DerivationHelper
	{
		public DerivationHelper(IChartLicense license, IReadOnlyList<IDerivation> dtrs, StartSymbol[] ss_matches)
		{
			this.license = license;
			this.ss_matches = ss_matches;
			this.ss = null;
			this.score = Double.NaN;
			this.dhash = 0;

			int dtr_count = dtrs == null ? 0 : dtrs.Count;
			Debug.Assert(license.DaughterArity == dtr_count);

			if (dtr_count == 0)
				daughters = Collection<IDerivation>.None;
			else if ((daughters = dtrs as IReadOnlyList<IDerivation>) == null)
			{
				var arr = new IDerivation[dtr_count];
				int i = 0;
				var e = dtrs.GetEnumerator();
				while (e.MoveNext())
					arr[i++] = e.Current;
				daughters = arr;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly IChartLicense license;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly IReadOnlyList<IDerivation> daughters;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly StartSymbol[] ss_matches;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		StartSymbol ss;

		public StartSymbol get_ss(IDerivation _this)
		{
			_this.DerivationTfs();
			return ss == StartSymbol.Null ? null : ss;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		Double score;
		public Double Score(IDerivation _this, MaxEntModel me_model)
		{
			if (Double.IsNaN(score))
				score = DerivationFuncs.Score(_this, me_model);
			return score;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		ulong dhash;
		public ulong DerivationHash(IDerivation _this)
		{
			return dhash != 0 ? dhash : (dhash = _this.HashCompute());
		}

		public bool _revalidate(Tfs tfs)
		{
			var _tmp = ss_matches;
			if (_tmp == null)
				return true;

			var sym = this.ss;
			if (sym != null)
				return sym != StartSymbol.Null;

			foreach (var ss_try in _tmp)
				if (tfs.fsu.UnifyCheck(ss_try.Expanded, tfs))
				{
					this.ss = ss_try;
					return true;
				}
			this.ss = StartSymbol.Null;
			return false;
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// IDerivation helper functions
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public static class DerivationFuncs
	{
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static bool IsValidRoot(this IDerivation _this)
		{
			return _this.MatchedStartSymbols != null && _this.ItemStartSymbol != null;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static bool HasRootMatches(this IDerivation _this)
		{
			return _this.MatchedStartSymbols != null;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static Double Score(this IDerivation _this, MaxEntModel me_model)
		{
			if (me_model == null && (me_model = (MaxEntModel)P.MaxEntModel.GetValue(_this)) == null)
				return Double.NaN;

			return me_model.ExtractTemplate1FeatureValues(_this).Sum();
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static String ScoreDetail(this IDerivation _this, MaxEntModel me_model, TextWriter tw)
		{
			String s = "";
#if _20130118
			foreach (var sd in me_model.ExtractTemplate1FeatureValuesExt(_this))
				s += sd.ToString(tw == Console.Out) + Environment.NewLine;
			if (tw == Console.Out)
				tw.WriteLineColor(s);
			else if (tw != null)
				tw.WriteLine(s);
#endif
			return s;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Symmetrical trees have value 0.0. Right-branching has positive value (max 1.0), Left-branching has negative value (min -1.0).
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static Double Symmetry(this IDerivation _this)
		{
			var vals = new List<Pairing<Double>>();
			NodeWeight(_this, vals);
			return vals.Count <= 0 ? 0 : vals.Select(p => p.x * p.y).Sum() / vals.Select(p => p.x).Sum();
		}

		static int NodeWeight(IDerivation deriv, List<Pairing<Double>> vals)
		{
			var dtrs = deriv.Daughters;
			int c = dtrs.Count;

			if (c == 0)
			{
				return 1;
			}
			else if (c == 1)
			{
				return NodeWeight(dtrs[0], vals);
			}
			else
			{
				int lnodes = NodeWeight(dtrs[0], vals);
				int rnodes = NodeWeight(dtrs[dtrs.Count - 1], vals);

				int sum = lnodes + rnodes;
				if (sum > 2)
				{
					vals.Add(new Pairing<double>(sum - 2, (rnodes - lnodes) / (double)(sum - 2)));
				}
				return sum;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static Double MrsScore(this IDerivation _this)
		{
			mrs.Mrs mrs = _this.DerivationTfs().Mrs();
			return mrs != null ? MrsRanking.ScoreMrs(mrs) : double.NaN;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static IEnumerable<String> ReadBack(this IDerivation _this)
		{
			return _readback(_this, false);
		}

		static IEnumerable<String> _readback(IDerivation _this, bool f_spelling_changed)
		{
			IChartLicense ent = _this.ChartLicense;
			LexicalRule lrule;
			ILexeme l;

			if ((l = ent as ILexeme) != null)
			{
				if (l is GenericLexicalEntry)
					yield return l.ReadbackTokensForm(_this.DerivationTfs());
				else
					yield return f_spelling_changed ? l.ReferenceForm : l.ReadbackTokensForm(_this.DerivationTfs());
			}
			else if ((lrule = _this.ChartLicense as LexicalRule) != null)
			{
				var daughter_strs = _readback(_this.Daughters[0], lrule.IsSpellingChange).ToArray();

				String mw;
				if (lrule.IsSpellingChange && (mw = lrule.morph_word(daughter_strs[0])) != null)
					daughter_strs[0] = mw;

				foreach (var ss in daughter_strs)
					yield return ss;
			}
			else
			{
				foreach (var q in _this.Daughters)
					foreach (var ss in _readback(q, false))
						yield return ss;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// ctrl can be null.
		/// ignores the tokenizer if the surface string is available
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static String Text(this IDerivation _this)
		{
			IString iss;

			if ((iss = _this as IString) != null)
				return iss.Text;

			ITokenizer itok = _this.FindTrace<ITokenizer>();
			if (itok == null)
			{
				var le = _this.FindTrace<LexicalEntry>();
				if (le != null)
					itok = le.Tokenizer;

				var hgb = _this.FindTrace<has_grammar_base>();
				if (hgb != null && hgb.em != null && hgb.em.lex != null)
					itok = hgb.em.lex.Tokenizer ?? hgb.em.DefaultTokenizer;

				if (itok == null)
					itok = SplitTokenizer.SpaceCharTokenizer;
			}

			return itok.MakeSurface(ReadBack(_this));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static ReadOnlyDictionary<IDerivation, ChartSpan> DaughterSpans(this IDerivation _this)
		{
			return new _dtr_span_helper(_this).Result;
		}

		struct _dtr_span_helper
		{
			struct dv_span
			{
				public IDerivation deriv;
				public ChartSpan sp;
			}

			public _dtr_span_helper(IDerivation dv_top)
				: this()
			{
				Result = Recurse(dv_top)
						.ToArray()	/// prevent counting pass in ReadOnlyDictionary constructor because Recurse() has side-effects
						.ToReadOnlyDictionary(dvs => dvs.deriv, dvs => dvs.sp);
			}
			public ReadOnlyDictionary<IDerivation, ChartSpan> Result;
			int i;

			IEnumerable<dv_span> Recurse(IDerivation dv)
			{
				if (dv.Daughters.Count == 0)
					yield return new dv_span { deriv = dv, sp = new ChartSpan(i, i++) };
				else
				{
					int zMin = int.MaxValue, zMax = int.MinValue;
					for (int j = 0; j < dv.Daughters.Count; j++)
					{
						IDerivation dtr = dv.Daughters[j];
						foreach (var ds in Recurse(dtr))
						{
							if (ds.sp.StartIndex < zMin)
								zMin = ds.sp.StartIndex;
							if (ds.sp.EndIndex > zMax)
								zMax = ds.sp.EndIndex;
							yield return ds;
						}
					}
					yield return new dv_span { deriv = dv, sp = new ChartSpan(zMin, zMax) };
				}
			}
		};


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static IEnumerable<IDerivation> Descendants(this IDerivation _this)
		{
			foreach (var dtr in _this.Daughters)
			{
				yield return dtr;
				foreach (var dd in dtr.Descendants())
					yield return dd;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static IEnumerable<IDerivation> DescendantsAndSelf(this IDerivation _this)
		{
			if (_this.Daughters.Count == 0)
				return new[] { _this };
			return _this.Descendants().Append(_this);
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static IEnumerable<IChartLicense> LicensesApplied(this IDerivation _this)
		{
			yield return _this.ChartLicense;
			foreach (var dtr in _this.Daughters)
				foreach (var icl in dtr.LicensesApplied())
					yield return icl;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Turns out it's not so trivial to get a reliable hash that is fixed for a given subtree, but maintains 
		/// positional distinctness of sub-derivations when nested recursively in any/all arbitrary future
		/// (unforeseen) contexts. The solution here is progressively change the rotation of the daughter 
		/// hashes (i.e. by argument position) while stamping the hash of the mother rule ('z') into a fixed 
		/// position (relative to the daughter) every time.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static ulong HashCompute(this IDerivation _this)
		{
			ulong z, ul = z = (ulong)_this.ChartLicense.Name.GetHashCode() << 16;
			var dtrs = _this.Daughters;
			for (int i = 0; i < dtrs.Count; i++)
			{
				int rot = i + 23;
				ul = (ul << rot) | (ul >> (64 - rot));
				ul += dtrs[i].DerivationHash ^ z;
			}
			return ul;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// todo: ? if there were no packings, what do we actually need to re-unify?
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static Tfs reconstitute_tfs(this IDerivation _this, TfsUnifier u)
		{
			Rule r = (Rule)_this.ChartLicense;

			var tdn = _this.Daughters;
			var rdn = r.DaughterNodes;

#if DEBUG
			Debug.Assert(rdn.Length == tdn.Count);

			var co = _this as IChartObj;
			if (co != null && !co.Tfs.SemanticsRestricted)
				throw new Exception();
#endif
			Tfs upper;
			Tfs d;

			if (r.DaughterArity == 1)
			{
				d = tdn[0].DerivationTfs();
				if (d == null)
					return null;
				if (d.SemanticsRestricted)
					throw new Exception();
				upper = u.UnifySection(rdn[0], d, Tfs.Flags.DeleteArgs);
			}
			else
			{
				/// unify all daughters at once

				var dtrs = new Tfs[tdn.Count];

				for (int i = 0; i < dtrs.Length; i++)
				{
					d = tdn[i].DerivationTfs();
					if (d == null)
						return null;
					if (d.SemanticsRestricted)
						throw new Exception();
					dtrs[i] = d;
				}

				upper = u.UnifyAllDaughters(r.Expanded, dtrs);
			}
			if (upper == null)
				return null;
			upper._set_trace(_this);

			//upper.Name = String.Format("{0}-d{1:X}", /*jctrl.SysObjName*/"chart", upper.id);
			return upper;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		static String fmt_basic(IDerivation d, bool f_color)
		{
			var s = "";

			if (f_color)
				s += String.Format("$red#{0:X}$gray", d.DerivationHash);
			else
				s += String.Format("#{0:X}", d.DerivationHash);

			var ias = d as IAtomicSequence;
			var sas = ias != null ? ias.StatusCode() : "?";
			s += "-" + (f_color ? "$red" + sas + "$" : sas);

			var ipk = d as IPacking;
			if (ipk != null)
				s += "-" + (ipk.PackedEdges == null ? "0" : ipk.PackedEdges.Count.ToString());

			return s;
		}

		static String fmt_ctx(IDerivation d, bool f_color = false)
		{
			String s = "", stok = null;
			if (d is IChartObj<ChartSpan>)
				stok = ((IChartObj<ChartSpan>)d).ProximalContext.ToString();
			else if (d is IChartObj<CoverageMap>)
				stok = ((IChartObj<CoverageMap>)d).ProximalContext.ToString();

			if (stok != null)
				s += (f_color ? "$cyan" + stok + "$" : stok);

			return s;
		}

		public static String TreeDisplay(this IDerivation d, bool f_color, IDerivation top, MaxEntModel me)
		{
			String s = "";

			//s = d.GetHashCode().ToString("X") + " ";

			s += fmt_ctx(d, f_color);

			s += " " + fmt_basic(d, f_color);

			var ipk = d as IPacking;
			if (ipk != null)
			{
				if (ipk.PackedEdges != null && ipk.PackedEdges.Count > 0)
					s += " pack{" + ipk.PackedEdges.Select(dd => fmt_basic(dd, f_color)).StringJoin(", ") + "}";
				else
					s += " no-pack";
			}

			var dtrs = d.Daughters;
			if (dtrs.Count > 0)
				s += " dtrs[" + dtrs.Select(dd => fmt_basic(dd, f_color)).StringJoin(", ") + "]";
			else
				s += " no-dtrs";

			s += " " + (f_color ? "$darkgreen" + d.ChartLicense.Name + "$" : d.ChartLicense.Name);

			s += String.Format(" (a{0})", d.ChartLicense.DaughterArity);

			String txt;
			if (d is ILexeme && !String.IsNullOrEmpty(txt = d.Text()))
			{
				txt = "\"" + txt + "\"";
				s += " " + (f_color ? "$darkyellow" + txt + "$" : txt);
			}

			var sts = d.GetType()._Name();
			s += " " + (f_color ? "$darkblue" + sts + "$" : sts);

			if (me != null && top != null)
			{
				double _s;
				if (double.IsNaN(_s = d.Score(me)))
				{
#if _20130118
					_s = me.ExtractTemplate1FeatureValuesExt(top).SingleOrDefault(sd => sd.node == d).Total;
					if (!double.IsNaN(_s))
					{
						var sds = _s.ToString();
						s += " " + (f_color ? "$darkgreen" + sds + "$" : sds);
					}
#endif
				}
			}

			s += Environment.NewLine;
			foreach (IDerivation deriv in d.Daughters)
				s += deriv.TreeDisplay(f_color, top, null).Indent(4) + Environment.NewLine;
			return s;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static string SimpleTreeDisplay(this IDerivation d)
		{
			String s = d.ChartLicense.Name;

			String txt;
			if (d is ILexeme && !String.IsNullOrEmpty(txt = d.Text()))
				s += " \"" + txt + "\"";

			s += Environment.NewLine;

			foreach (IDerivation deriv in d.Daughters)
				s += SimpleTreeDisplay(deriv).Indent(4) + Environment.NewLine;
			return s;
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static String ToString(this IDerivation _this, bool f_color)
		{
			String cn = _this.GetType().Name;

			if (f_color && _this.IsValidRoot())
				cn = String.Format("$green {0}({1})$ ", cn, _this.ItemStartSymbol.Name);

			ITokenizer tok = (ITokenizer)P.Tokenizer.GetValue(_this);
			var rb = _this.ReadBack();
			String txt = tok == null ? rb.StringJoin(" ") : tok.MakeSurface(rb);
			String surf = String.Format(f_color ? "$yellow {0}" : "\"{0}\"", txt);

			String s = String.Format("#{0:X} ({1:X16}) {2} {3}",
							0,//_this.Id,
							_this.DerivationHash,
							cn,
							surf);
			//if (this.daughters.Count != 0)
			{
				s += Environment.NewLine;
				s += _this.TreeDisplay(f_color, _this as IDerivation, null);
			}
			return s;
		}
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public sealed class DerivationComparer : IEqualityComparer<IDerivation>, IComparer<IDerivation>, IComparer<mrs.Mrs>
	{
		public static readonly DerivationComparer Instance;

		static DerivationComparer() { Instance = new DerivationComparer(); }

		DerivationComparer() { }

		public bool Equals(IDerivation x, IDerivation y)
		{
			if ((Object)x == (Object)y)
				return true;

			int c;
			IReadOnlyList<IDerivation> dx, dy;

			if ((Object)x == null || (Object)y == null || x.ChartLicense != y.ChartLicense ||
				(c = (dx = x.Daughters).Count) != (dy = y.Daughters).Count)
				return false;

			for (int i = 0; i < c; i++)
				if (!Equals(dx[i], dy[i]))
					return false;

			return true;
		}

		public int GetHashCode(IDerivation d)
		{
			ulong h = d.DerivationHash;
			return (int)(h >> 32) ^ (int)h;
		}

		public int Compare(IDerivation x, IDerivation y)
		{
			var hx = x.DerivationHash;
			var hy = y.DerivationHash;
			if (hx == hy)
			{
				if (Equals(x, y))
					return 0;
				Debug.Print("derivation hash collision");
				return StringComparer.Ordinal.Compare(DerivationFuncs.SimpleTreeDisplay(x), DerivationFuncs.SimpleTreeDisplay(y));
			}

			var s1 = x.ParseSelectionScore;
			var s2 = y.ParseSelectionScore;
			if (double.IsNaN(s2))
			{
				if (!double.IsNaN(s1))
					return 1;
			}
			else if (double.IsNaN(s1))
				return -1;
			else
				return s1 > s2 ? -1 : 1;

			return hx > hy ? 1 : -1;
		}

		int IComparer<mrs.Mrs>.Compare(mrs.Mrs x, mrs.Mrs y)
		{
			var dx = x.FindTrace<IDerivation>();
			var dy = y.FindTrace<IDerivation>();
			if (dx == null || dy == null)
				throw new Exception();
			return Compare(dx, dy);
		}
	};
}
